/*
 * (c) Copyright 2020 CORSIKA Project, corsika-project@lists.kit.edu
 *
 * This software is distributed under the terms of the 3-clause BSD license.
 * See file LICENSE for a full version of the license.
 */

/*
 * uint128_t.inl
 *
 *  Created on: 13/03/2021
 *      Author: Antonio Augusto Alves Junior
 */

#pragma once

#include <cstring>

namespace random_iterator {

  const uint128_t uint128_0(0);
  const uint128_t uint128_1(1);

  inline uint128_t::uint128_t(std::string& s) { init(s.c_str()); }

  inline uint128_t::uint128_t(const char* s) { init(s); }

  inline void uint128_t::init(const char* s) {
    if (s == NULL || s[0] == 0) {
      LOWER = UPPER = 0;
      return;
    }

    while (*s == ' ') ++s;

    if (std::memcmp(s, "0x", 2) == 0) {
      _init_hex(&s[2]);
    } else if (std::memcmp(s, "0o", 2) == 0) {
      _init_oct(&s[2]);
    } else {
      _init_dec(s);
    }
  }

  inline void uint128_t::_init_hex(const char* s) {
    // 2**128 = 0x100000000000000000000000000000000.
    LOWER = UPPER = 0;
    int i;
    for (i = 0; *s && i < 16; ++s, ++i) {
      if ('0' <= *s && *s <= '9') {
        LOWER *= 16;
        LOWER += *s - '0';
      } else if ('A' <= *s && *s <= 'F') {
        LOWER *= 16;
        LOWER += *s + (10 - 'A');
      } else if ('a' <= *s && *s <= 'f') {
        LOWER *= 16;
        LOWER += *s + (10 - 'a');
      } else {
        return;
      }
    }
    for (; *s && i < 32; ++s, ++i) {
      if ('0' <= *s && *s <= '9') {
        *this *= 16;
        *this += *s - '0';
      } else if ('A' <= *s && *s <= 'F') {
        *this *= 16;
        *this += *s + (10 - 'A');
      } else if ('a' <= *s && *s <= 'f') {
        *this *= 16;
        *this += *s + (10 - 'a');
      } else {
        return;
      }
    }
  }

  inline void uint128_t::_init_dec(const char* s) {
    // 2**128 = 340282366920938463463374607431768211456.
    LOWER = UPPER = 0;
    for (int i = 0; '0' <= *s && *s <= '9' && i < 39; ++s, ++i) {
      *this *= 10;
      *this += *s - '0';
    }
  }

  inline void uint128_t::_init_oct(const char* s) {
    // 2**128 = 0o4000000000000000000000000000000000000000000.
    LOWER = UPPER = 0;
    for (int i = 0; '0' <= *s && *s <= '7' && i < 43; ++s, ++i) {
      *this *= 8;
      *this += *s - '0';
    }
  }

  inline uint128_t::operator bool() const { return (bool)(UPPER | LOWER); }

  inline uint128_t::operator uint8_t() const { return (uint8_t)LOWER; }

  inline uint128_t::operator uint16_t() const { return (uint16_t)LOWER; }

  inline uint128_t::operator uint32_t() const { return (uint32_t)LOWER; }

  inline uint128_t::operator uint64_t() const { return (uint64_t)LOWER; }

  inline uint128_t uint128_t::operator&(const uint128_t& rhs) const {
    return uint128_t(UPPER & rhs.UPPER, LOWER & rhs.LOWER);
  }

  inline uint128_t& uint128_t::operator&=(const uint128_t& rhs) {
    UPPER &= rhs.UPPER;
    LOWER &= rhs.LOWER;
    return *this;
  }

  inline uint128_t uint128_t::operator|(const uint128_t& rhs) const {
    return uint128_t(UPPER | rhs.UPPER, LOWER | rhs.LOWER);
  }

  inline uint128_t& uint128_t::operator|=(const uint128_t& rhs) {
    UPPER |= rhs.UPPER;
    LOWER |= rhs.LOWER;
    return *this;
  }

  inline uint128_t uint128_t::operator^(const uint128_t& rhs) const {
    return uint128_t(UPPER ^ rhs.UPPER, LOWER ^ rhs.LOWER);
  }

  inline uint128_t& uint128_t::operator^=(const uint128_t& rhs) {
    UPPER ^= rhs.UPPER;
    LOWER ^= rhs.LOWER;
    return *this;
  }

  inline uint128_t uint128_t::operator~() const { return uint128_t(~UPPER, ~LOWER); }

  inline uint128_t uint128_t::operator<<(const uint128_t& rhs) const {
    const uint64_t shift = rhs.LOWER;
    if (((bool)rhs.UPPER) || (shift >= 128)) {
      return uint128_0;
    } else if (shift == 64) {
      return uint128_t(LOWER, 0);
    } else if (shift == 0) {
      return *this;
    } else if (shift < 64) {
      return uint128_t((UPPER << shift) + (LOWER >> (64 - shift)), LOWER << shift);
    } else if ((128 > shift) && (shift > 64)) {
      return uint128_t(LOWER << (shift - 64), 0);
    } else {
      return uint128_0;
    }
  }

  inline uint128_t& uint128_t::operator<<=(const uint128_t& rhs) {
    *this = *this << rhs;
    return *this;
  }

  inline uint128_t uint128_t::operator>>(const uint128_t& rhs) const {

    const uint64_t shift = rhs.LOWER;
    if (((bool)rhs.UPPER) || (shift >= 128)) {
      return uint128_0;
    } else if (shift == 64) {
      return uint128_t(0, UPPER);
    } else if (shift == 0) {
      return *this;
    } else if (shift < 64) {
      return uint128_t(UPPER >> shift, (UPPER << (64 - shift)) + (LOWER >> shift));
    } else if ((128 > shift) && (shift > 64)) {
      return uint128_t(0, (UPPER >> (shift - 64)));
    } else {
      return uint128_0;
    }
  }

  inline uint128_t& uint128_t::operator>>=(const uint128_t& rhs) {
    *this = *this >> rhs;
    return *this;
  }

  inline bool uint128_t::operator!() const { return !(bool)(UPPER | LOWER); }

  inline bool uint128_t::operator&&(const uint128_t& rhs) const {
    return ((bool)*this && rhs);
  }

  inline bool uint128_t::operator||(const uint128_t& rhs) const {
    return ((bool)*this || rhs);
  }

  inline bool uint128_t::operator==(const uint128_t& rhs) const {
    return ((UPPER == rhs.UPPER) && (LOWER == rhs.LOWER));
  }

  inline bool uint128_t::operator!=(const uint128_t& rhs) const {
    return ((UPPER != rhs.UPPER) | (LOWER != rhs.LOWER));
  }

  inline bool uint128_t::operator>(const uint128_t& rhs) const {
    if (UPPER == rhs.UPPER) { return (LOWER > rhs.LOWER); }
    return (UPPER > rhs.UPPER);
  }

  inline bool uint128_t::operator<(const uint128_t& rhs) const {
    if (UPPER == rhs.UPPER) { return (LOWER < rhs.LOWER); }
    return (UPPER < rhs.UPPER);
  }

  inline bool uint128_t::operator>=(const uint128_t& rhs) const {
    return ((*this > rhs) || (*this == rhs));
  }

  inline bool uint128_t::operator<=(const uint128_t& rhs) const {
    return ((*this < rhs) || (*this == rhs));
  }

  inline uint128_t uint128_t::operator+(const uint128_t& rhs) const {
    return uint128_t(UPPER + rhs.UPPER + ((LOWER + rhs.LOWER) < LOWER),
                     LOWER + rhs.LOWER);
  }

  inline uint128_t& uint128_t::operator+=(const uint128_t& rhs) {
    UPPER += rhs.UPPER + ((LOWER + rhs.LOWER) < LOWER);
    LOWER += rhs.LOWER;
    return *this;
  }

  inline uint128_t uint128_t::operator-(const uint128_t& rhs) const {
    return uint128_t(UPPER - rhs.UPPER - ((LOWER - rhs.LOWER) > LOWER),
                     LOWER - rhs.LOWER);
  }

  inline uint128_t& uint128_t::operator-=(const uint128_t& rhs) {
    *this = *this - rhs;
    return *this;
  }

  inline uint128_t uint128_t::operator*(const uint128_t& rhs) const {

#ifdef __powerpc64__
    return mul128(*this, rhs);
#elif __x86_64__
    return mul128(*this, rhs);
#else

    // split values into 4 32-bit parts
    uint64_t top[4] = {UPPER >> 32, UPPER & 0xffffffff, LOWER >> 32, LOWER & 0xffffffff};
    uint64_t bottom[4] = {rhs.UPPER >> 32, rhs.UPPER & 0xffffffff, rhs.LOWER >> 32,
                          rhs.LOWER & 0xffffffff};
    uint64_t products[4][4];

    // multiply each component of the values
    for (int y = 3; y > -1; y--) {
      for (int x = 3; x > -1; x--) { products[3 - x][y] = top[x] * bottom[y]; }
    }

    // first row
    uint64_t fourth32 = (products[0][3] & 0xffffffff);
    uint64_t third32 = (products[0][2] & 0xffffffff) + (products[0][3] >> 32);
    uint64_t second32 = (products[0][1] & 0xffffffff) + (products[0][2] >> 32);
    uint64_t first32 = (products[0][0] & 0xffffffff) + (products[0][1] >> 32);

    // second row
    third32 += (products[1][3] & 0xffffffff);
    second32 += (products[1][2] & 0xffffffff) + (products[1][3] >> 32);
    first32 += (products[1][1] & 0xffffffff) + (products[1][2] >> 32);

    // third row
    second32 += (products[2][3] & 0xffffffff);
    first32 += (products[2][2] & 0xffffffff) + (products[2][3] >> 32);

    // fourth row
    first32 += (products[3][3] & 0xffffffff);

    // move carry to next digit
    third32 += fourth32 >> 32;
    second32 += third32 >> 32;
    first32 += second32 >> 32;

    // remove carry from current digit
    fourth32 &= 0xffffffff;
    third32 &= 0xffffffff;
    second32 &= 0xffffffff;
    first32 &= 0xffffffff;

    // combine components
    return uint128_t((first32 << 32) | second32, (third32 << 32) | fourth32);
#endif
  }

  inline uint128_t& uint128_t::operator*=(const uint128_t& rhs) {
    *this = *this * rhs;
    return *this;
  }

  inline std::pair<uint128_t, uint128_t> uint128_t::divmod(const uint128_t& lhs,
                                                           const uint128_t& rhs) const {
    // Save some calculations /////////////////////
    if (rhs == uint128_0) {
      throw std::domain_error("Error: division or modulus by 0");
    } else if (rhs == uint128_1) {
      return std::pair<uint128_t, uint128_t>(lhs, uint128_0);
    } else if (lhs == rhs) {
      return std::pair<uint128_t, uint128_t>(uint128_1, uint128_0);
    } else if ((lhs == uint128_0) || (lhs < rhs)) {
      return std::pair<uint128_t, uint128_t>(uint128_0, lhs);
    }

    std::pair<uint128_t, uint128_t> qr(uint128_0, uint128_0);
    for (uint8_t x = lhs.bits(); x > 0; x--) {
      qr.first <<= uint128_1;
      qr.second <<= uint128_1;

      if ((lhs >> (x - 1U)) & 1) { ++qr.second; }

      if (qr.second >= rhs) {
        qr.second -= rhs;
        ++qr.first;
      }
    }
    return qr;
  }

  inline uint128_t uint128_t::operator/(const uint128_t& rhs) const {
    return divmod(*this, rhs).first;
  }

  inline uint128_t& uint128_t::operator/=(const uint128_t& rhs) {
    *this = *this / rhs;
    return *this;
  }

  inline uint128_t uint128_t::operator%(const uint128_t& rhs) const {
    return divmod(*this, rhs).second;
  }

  inline uint128_t& uint128_t::operator%=(const uint128_t& rhs) {
    *this = *this % rhs;
    return *this;
  }

  inline uint128_t& uint128_t::operator++() { return *this += uint128_1; }

  inline uint128_t uint128_t::operator++(int) {
    uint128_t temp(*this);
    ++*this;
    return temp;
  }

  inline uint128_t& uint128_t::operator--() { return *this -= uint128_1; }

  inline uint128_t uint128_t::operator--(int) {
    uint128_t temp(*this);
    --*this;
    return temp;
  }

  inline uint128_t uint128_t::operator+() const { return *this; }

  inline uint128_t uint128_t::operator-() const { return ~*this + uint128_1; }

  inline uint64_t uint128_t::upper() const { return UPPER; }

  inline uint64_t uint128_t::lower() const { return LOWER; }

  inline uint8_t uint128_t::bits() const {
    uint8_t out = 0;
    if (UPPER) {
      out = 64;
      uint64_t up = UPPER;
      while (up) {
        up >>= 1;
        out++;
      }
    } else {
      uint64_t low = LOWER;
      while (low) {
        low >>= 1;
        out++;
      }
    }
    return out;
  }

  inline uint128_t uint128_t::rotate_right() const { return uint128_t(LOWER, UPPER); }

  inline std::string uint128_t::str(uint8_t base, const unsigned int& len) const {
    if ((base < 2) || (base > 16)) {
      throw std::invalid_argument("Base must be in the range [2, 16]");
    }
    std::string out = "";
    if (!(*this)) {
      out = "0";
    } else {
      std::pair<uint128_t, uint128_t> qr(*this, uint128_0);
      do {
        qr = divmod(qr.first, base);
        out = "0123456789abcdef"[(uint8_t)qr.second] + out;
      } while (qr.first);
    }
    if (out.size() < len) { out = std::string(len - out.size(), '0') + out; }
    return out;
  }

  inline uint128_t operator<<(const bool& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator<<(const uint8_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator<<(const uint16_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator<<(const uint32_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator<<(const uint64_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator<<(const int8_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator<<(const int16_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator<<(const int32_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator<<(const int64_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) << rhs;
  }

  inline uint128_t operator>>(const bool& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline uint128_t operator>>(const uint8_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline uint128_t operator>>(const uint16_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline uint128_t operator>>(const uint32_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline uint128_t operator>>(const uint64_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline uint128_t operator>>(const int8_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline uint128_t operator>>(const int16_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline uint128_t operator>>(const int32_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline uint128_t operator>>(const int64_t& lhs, const uint128_t& rhs) {
    return uint128_t(lhs) >> rhs;
  }

  inline std::ostream& operator<<(std::ostream& stream, const uint128_t& rhs) {
    if (stream.flags() & stream.oct) {
      stream << rhs.str(8);
    } else if (stream.flags() & stream.dec) {
      stream << rhs.str(10);
    } else if (stream.flags() & stream.hex) {
      stream << rhs.str(16);
    }
    return stream;
  }

} // namespace random_iterator
